package xiaomin.demo.algorithm;
/*
返回 将 一 维 数组 向右 旋转 k 个 位置 的 结果。 比如， 一 维 数组{ 1, 2, 3, 4, 5}， k= 2 时，
 返回 结果是{ 4, 5, 1, 2, 3}。 要求 常数 级 空间 复杂度， 允许 修改 原有 数组。

陈东锋. 进军硅谷:程序员面试揭秘 (技术移民参考手册) (p. 64). 电子工业出版社. Kindle 版本.

思路：
翻转三次数组
1.整个数组翻转
2.k把数组分为左右两部分，左右两部分分别翻转

 */
public class Lesson04 {
    public static void run(int k){
        int[] a ={1,2,3,4,5};
        //如果k大于数组长度，对它取余
        if(k<0){
            System.out.println("参数必须大于0");
        }
        if(k>a.length){
            k=k%a.length;
        }
        //旋转以后，第一个位置的数字下标是　N-k，比如k是2，则第一个数字的下标是5-2=3
        int firstIndex=a.length-k;

        int[] result=new int[a.length];

        //错位复制
        for(int i=0;i<k;i++){
            result[i]=a[firstIndex+i];
        }
        for(int i=0;i<firstIndex;i++){
            result[k+i]=a[i];
        }
        System.out.println("复制法：");
        for(int x:result){
            System.out.println(x);
        }

        System.out.println("反转法：");
        reverse(a,0,a.length-1);
        for(int x:a){
            System.out.println(x);
        }
        reverse(a,0,k-1);
        for(int x:a){
            System.out.println(x);
        }
        reverse(a,k,a.length-1);
        for(int x:a){
            System.out.println(x);
        }
        System.out.println("反转法：");
        for(int x:a){
            System.out.println(x);
        }
    }

    public static void reverse(int[] a,int start,int end){
        while (start<end){
            int temp=a[start];
            a[start]=a[end];
            a[end]=temp;
            start++;
            end--;
        }
    }
}
